// 给定一个包含n+1个整数的数组nums，里边包含的值都在1-n之间，假设nums中只存在一个重复的整数，要求找出这个重复的数
// 要求使用空间复杂度为常数级，时间复杂度小于O(n平方)的解决方法

// 思路： 二分查找，该数组的元素都在1-n之间，且只有一个重复的，可以在1-n之间二分查找，判断条件是数组中的元素小于等于mid，则target要更大
// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
function findDuplicate(arr) {
    let n = arr.length
    let left = 1
    let right = n
    function count(target) {
        let count = 0
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] <= target) {
                count++
            }            
        }
        return count
    }
    while (left < right) {
        let mid = Math.floor((right - left) / 2) + left
        let c = count(mid)
        if (c <= mid) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

let arr = [8,9,1, 2, 2,3,,4,5,6,7, 10]
arr = [1,2,3,4]
console.log(findDuplicate(arr))